/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @see https://leetcode-cn.com/problems/balanced-binary-tree/
 * 判断是否是平衡二叉树
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
  if(!root) {
    return true;
  }
  if(!root.left && !root.right) {
    return true;
  }
  return height(root) >= 0 ;
};

function height(root) {
  console.log('root', root)
  if(!root) {
    return 0;
  }
  // if(!root.left && !root.right) {
  //   return 1;
  // }
  let leftHeight  = height(root.left); // 1
  let rightHeight = height(root.right); // 
  console.log(root, leftHeight, rightHeight)
  if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {
    return Math.max(leftHeight , rightHeight) + 1;
  } else {
    return -1;
  }
}

var tree = {
  val: 3,
  left: {
    val: 9,
    right: {
      val: 88
    }
  },
  right: {
    val: 30,
    left: {
      val: 15
    },
    right: {
      val: 7,
      right: {
        val: 89
      }
    }
  }
}


var isBalanced2 = function(root) {
  function balance(node) {
    if(!node) {
      return 0
    }
    let left = balance(node.left);
    let right = balance(node.right);
    return Math.max(left, right) + 1;
  }
  if(!root) {
    return true;
  }
  if(Math.abs(balance(root.left) - balance(root.right)) > 1) {
    return false;
  }
  return isBalanced2(root.left) && isBalanced2(root.right);
}

console.log(isBalanced2(tree));
console.log(isBalanced(tree));